#ifndef _BUOLA_GRAPH_DIJKSTRA_H_
#define _BUOLA_GRAPH_DIJKSTRA_H_

#include <buola/graph/cgraph.h>
#include "properties.h"
#include <buola/algorithm/range.h>
#include <boost/graph/dijkstra_shortest_paths.hpp>

namespace buola { namespace graph {

template<typename tGraph,typename tWeightMap,typename tDistanceMap>
void dijkstra_shortest_distance(tGraph &&pGraph,typename ODecay<tGraph>::vertex_descriptor pOrigin,tWeightMap &&pWeights,
                                tDistanceMap &&pDistances)
{
    boost::dijkstra_shortest_paths(std::forward<tGraph>(pGraph),pOrigin,boost::weight_map(std::forward<tWeightMap>(pWeights)).
                                   distance_map(std::forward<tDistanceMap>(pDistances)));
}
                
template<typename tGraph,typename tWeightMap>
std::vector<typename tGraph::vertex_descriptor> dijkstra_shortest_path(const tGraph &pGraph,
                     typename tGraph::vertex_descriptor pFrom,typename tGraph::vertex_descriptor pTo,const tWeightMap &pWeight)
{
    auto lPredecessor=new_vertex_property<typename tGraph::vertex_descriptor>(pGraph);
    
    boost::dijkstra_shortest_paths(pGraph,pFrom,boost::weight_map(pWeight).predecessor_map(lPredecessor.Map()));
    
    ///\todo for undirected graphs, the reverse path can be found, and it is not necessary to reverse
    std::vector<typename tGraph::vertex_descriptor> lPath;
    auto lNode=pTo;
    lPath.push_back(lNode);
    while(lNode!=pFrom)
    {
        auto lPre=lPredecessor[lNode];
        if(lPre==lNode)
        {
            lPath.clear();
            break;
        }
        lNode=lPre;
        lPath.push_back(lNode);
    }
    
    reverse(lPath);
    return lPath;
}
                
/*namespace graph*/ } /*namespace buola*/ }

#endif
